Problem statement: zenit17kkh

Hravý zárobok

Počet bodov: 30, časový limit: 500ms

Cez víkend bol Roman v kaštieli svojho zbohatlého strýka Držgroša. Ten z neho chcel vyžmýkať čo najviac lacnej pracovnej sily a tak Roman nemal chvíľku oddychu od domácich prác – vyleštiť každú mincu v strýkovej pokladni, umyť starodávne čínske vázy, vyleštiť každú mincu v strýkovej pokladni, povysávať perzské koberce, vyleštiť každú mincu v strýkovej pokladni…

Po dlhom prehováraní a vyhrážaní si však Roman aspoň vynútil od strýka Držgroša, aby mu za jeho odpracovaný víkend dal nejaké vreckové. Strýko Držgroš Romanovi teda vypísal šek. Keďže nemal práve po ruke kalkulačku a Romanovi matika až tak nejde, namiesto sumy na šek napísal za každú domácu prácu nejakú výplatu, a medzi ne napísal pluská. Teda za horeuvedené domáce práce Držgroš na šek mohol napísať napríklad \(2+2+2+2+2\), takže by Romanovi v banke vyplatili 10 eur.

Roman však dostal super nápad. K plusku stačí dopísať dve čiarky a je z toho násobenie – \(*\)! Z tohto šeku by teda namiesto 10 eur vedel dostať až \(2*2*2*2*2\) = 32 eur! Už-už si chcel v banke vypýtať vylepšené vreckové, keď ho napadlo niečo ešte lepšie – veď by si najprv od banky mohol vyžiadať, aby mu šek prepísala. Banka je Romanovi ochotná prepísať šek na iný, v rovnakom formáte ako ho vypísal Držgroš. Súčet na novom šeku musí byť rovnaký, ako na tom, ktorý dostal od strýka. Netušiac, aký trik má Roman v úmysle, nechala banka na Romanovi, aby si určil, aké čísla na šeku vlastne budú. Roman by si teda horeuvedený šek mohol nechať prepísať na \(3+2+3+2\), čo by na inej pobočke mohol zinkasovať ako \(3*2*3*2\) = 36 eur!

Odkedy si vymyslel túto techniku, chodil, na strýkovo veľké prekvapenie, na návštevu skoro každý víkend. Vždy však dostával rôznu výplatu a už ho nebavilo lámať si hlavu nad tým, koľko vlastne dokáže zo svojej výplaty naozaj ‘zarobiť’. Zišiel by sa mu na to program…

Vstup a výstup

V jedinom riadku vstupu je celé číslo \(1 \leq n\) – koľko dostal Roman od Držgroša zaplatené.

Nájdite najväčší zárobok, ktorý dokáže Roman získať zo šeku s hodnotou \(n\) – teda najväčšie číslo \(v\) také, že \(v = a_1 * a_2 * \cdots * a_k\) pre nejaké \(k > 0\) a \(n = a_1 + a_2 + \cdots + a_k\), pričom \(a_i\) sú kladné celé čísla. Keďže toto číslo môže byť veľmi veľké, vypíšte ho modulo \(10^9+7\).

V testovacích sadách sú maximálne hodnoty \(n\) postupne \(50, 5000, 10^5, 10^9, 10^{18}\).

Príklad

Input:

10

Output:

36